package 力扣_树算法.二叉树;


/**654. 最大二叉树
 * @author zx
 * @create 2022-04-14 16:14
 */
public class Num654 {
    /**
     * @return 代码可以看懂,但是自己做还是有点难度的
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums,0,nums.length - 1);
    }
    //递归语义：找出在数组[left,right]中二叉树的根节点
    private TreeNode construct(int[] nums, int left, int right){
        if(left > right){
            return null;
        }
        int maxIndex = maxValueIndex(nums,left,right);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = construct(nums,left,maxIndex - 1);
        root.right = construct(nums,maxIndex + 1,right);
        return root;
    }
    //找到数组[left,right]上的最大值的下标
    private int maxValueIndex(int[] nums,int left,int right){
        int maxIndex = left;
        for(int i = left;i <= right;i++){
            if(nums[i] > nums[maxIndex]){
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
